package algorithm;

/**
 * 回文字符串,
 * 情况一： i 在 R 外暴力扩
 * 情况二： i 在 R 内，取对称点i‘，并得到对称点的回文半径pArr[2C-i],拿R-i跟它之间取最小值，再去手动扩，给对应节点的回文半径+1，
 */
public class Manacher {
    public static char[] manacherString(String str) {
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i&1) == 0 ? '#' : str.charAt(index++);
        }
        return res;
    }
    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int C = -1;
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < charArr.length; i++) {
            // i在R里面
            pArr[i] = R > i ? Math.min(pArr[2*C - i], R - i) : 1;
            while(i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i+pArr[i]] == charArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;

    }

    public static void main(String[] args) {

    }
}
